/*************************************************************************
> File Name: doublePotiner.cpp
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2024-01-16 22:36:14
> Description:
42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，
计算按此排列的柱子，下雨之后能接多少雨水。
************************************************************************/

// 思路： 双指针
// 左右指针指向两侧,进行夹逼,
// 当两边高低互换时,形成一个水平面
// 统计该水平面
//

#include <vector>
using namespace std;

class Solution
{
public:
    int trap(vector<int> &height)
    {
        int length = height.size();
        if (length == 0)
        {
            return 0;
        }
        int left = 1, right = length - 2, sum = 0;
        int left_wall = 0, right_wall = 0;
        for (int i = 1; i < length - 1; i++) // 执行 i 次 从两边向中间遍历
        {
            if (height[left - 1] < height[right + 1])
            {
                left_wall = max(left_wall, height[left - 1]);
                if (left_wall > height[left])
                {
                    sum += left_wall - height[left];
                }
                left++; // 靠近
            }
            else
            {
                right_wall = max(right_wall, height[right+1]);
                if (right_wall > height[right])
                {
                    sum += right_wall - height[right];
                }
                right--;
            }
        }
        return sum;
    }
};